<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      const swap = (array, a, b) => {
        const temp = array[a];
        array[a] = array[b];
        array[b] = temp;
      };

      /* 
      插入排序每次排一个数组项，以此方式构建最后的排序数组。
      插入排序性能优于冒泡选择排序
      */

      function insertSort(array) {
        const { length } = array;

        let temp; // 存放当前这一轮索引的元素值
        // 从第二项开始 往前对比
        for (let i = 1; i < length; i++) {
          temp = array[i];
          let j = i; // 一个标记  第1轮往前比较1次 第2轮往前比较2次
          // 终止循环条件 j > 0 或者 前一项不大于当前项
          while (j > 0 && array[j - 1] > temp) {
            // 关键 覆盖位置  如果前一项>后一项  那么前一项就覆盖了前一项  临时变量tem存的值再回填
            array[j] = array[j - 1];
            j--;
          }
          array[j] = temp;
        }

        console.log(array);
      }

      insertSort([3, 2, 1]); 
      /* 
      排序的过程:
      [3, 2, 1]  ->  [2, 3, 1]  ->  [1, 2, 3]
      */
    </script>
  </body>
</html>
